|
In computer science, in particular in formal language theory, the pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages. It generalizes the pumping lemma for regular languages. == Formal statement == If a language ''L'' is context-free, then there exists some integer ''p'' ≥ 1 (called a "pumping length") such that every string ''s'' in ''L'' that has a length of ''p'' or more symbols (i.e. with |''s''| ≥ ''p'') can be written as : ''s'' = ''uvwxy'' with substrings ''u'', ''v'', ''w'', ''x'' and ''y'', such that : 1. |''vwx''| ≤ ''p'', : 2. |''vx''| ≥ 1, and : 3. ''uvnwxny'' is in ''L'' for all ''n'' ≥ 0. Below is a formal expression of the Pumping Lemma. ∀''L''⊆Σ *. (context_free(''L'') ⇒ ∃''p''≥1. ∀''s''∈''L''. (|''s''|≥''p'' ⇒ ∃''u'',''v'',''w'',''x'',''y''∈Σ *. (''s''=''uvwxy'' ∧ |''vwx''|≤''p'' ∧ |''vx''|≥1 ∧ ∀''n''≥0. ''uvnwxny''∈''L''))) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pumping lemma for context-free languages」の詳細全文を読む スポンサード リンク
|